`
https://leetcode.cn/problems/gray-code/
`

/**
 * @param {number} n
 * @return {number[]}
 */
var grayCode = function (n) {
  let res = null
  const path = []
  const used = new Set()

  const traverse = (root) => {
    if (res !== null) {
      return;
    }

    if (path.length === (1 << n)) {
      res = [...path];
      return;
    }

    if (used.has(root)) {
      return;
    }

    // 多叉树遍历的前序位置
    used.add(root);
    path.push(root);

    // 对当前数字的每个二进制位进行翻转，得到子节点
    for (let i = 0; i < n; i++) {
      let next = flipBit(root, i);
      traverse(next);
    }

    // 多叉树遍历的后序位置
    used.delete(root);
    path.pop();
  };

  traverse(0)

  return res
};

// 把第 i 位取反（0 变 1，1 变 0）
var flipBit = function (x, i) {
  return x ^ (1 << i);
};